#ifndef PW_PBL_MATH_HPP
#define PW_PBL_MATH_HPP

#include <cstdint>
#include <cassert>
#include <bit>
#include <climits>
#include <type_traits>
#include <utility>
#include <concepts>
#include "BitInt.hpp"
#include "Throw.hpp"

namespace pw_pbl::Math
{
	template <std::integral T1, std::integral T2, std::integral RESULT>
	constexpr bool AddOverflow(T1 t1, T2 t2, RESULT *result) noexcept { return __builtin_add_overflow(t1, t2, result); }

	template <std::integral T1, std::integral RESULT>
	constexpr bool AddOverflow(T1 t1, RESULT *result) noexcept { return __builtin_add_overflow(t1, *result, result); }

	template <std::integral T1, std::integral T2, std::integral RESULT>
	constexpr bool SubOverflow(T1 t1, T2 t2, RESULT *result) noexcept { return __builtin_sub_overflow(t1, t2, result); }

	template <std::integral T1, std::integral RESULT>
	constexpr bool SubOverflow(T1 t1, RESULT *result) noexcept { return __builtin_sub_overflow(t1, *result, result); }

	template <std::integral T1, std::integral T2, std::integral RESULT>
	constexpr bool MulOverflow(T1 t1, T2 t2, RESULT *result) noexcept { return __builtin_mul_overflow(t1, t2, result); }

	template <std::integral T1, std::integral RESULT>
	constexpr bool MulOverflow(T1 t1, RESULT *result) noexcept { return __builtin_mul_overflow(t1, *result, result); }

	/// 强制要求指定值是常量求值
	template <auto V>
	static constexpr auto Const = V;

	template <typename T>
	constexpr T Abs(T v) noexcept
	{
		if constexpr (std::is_signed_v<T>)
			return v < 0 ? -v : v;
		else
			return v;
	}

	/// 判断一个数是否是2的幂
	/// @note 值为0时结果也为true
	template <typename T>
	constexpr bool IsPow2(T x) noexcept { return (x & (x - 1)) == 0; }

	/// 指定值的Log2值
	template <auto V>
	requires(IsPow2(V) && V > 0) constexpr auto Log2 = sizeof(V) * CHAR_BIT - 1 - std::countl_zero(std::make_unsigned_t<decltype(V)>(V));

	/// log2运算常函数，截断取整，输入应大于0
	template <typename T>
	constexpr T Log2Floor(T num) noexcept
	{
		if (std::is_constant_evaluated() && num <= 0)
			Throw("0以下的log2无意义");
		return sizeof(T) * CHAR_BIT - 1 - std::countl_zero(std::make_unsigned_t<T>(num));
	}

	/// log2运算常函数，向上取整，输入应大于0
	template <typename T>
	constexpr T Log2Ceil(T num) noexcept
	{
		if (std::is_constant_evaluated() && num <= 0)
			Throw("0以下的log2无意义");
		using UT = std::make_unsigned_t<T>;
		if (IsPow2(num))
			return sizeof(T) * CHAR_BIT - 1 - std::countl_zero(UT(num));
		else
			return sizeof(T) * CHAR_BIT - std::countl_zero(UT(num));
	}

	/// exp2运算常函数
	template <typename T>
	constexpr auto Exp2(T num) noexcept
	{
		if (std::is_constant_evaluated() && num >= sizeof(T) * CHAR_BIT)
			Throw("数值超限");
		return T(1) << num;
	}

	/// Log函数常函数，向上取整
	template <typename T>
	constexpr T LogCeil(unsigned int base, T num)
	{
		if (base < 2 || num <= 0)
		{
			if (std::is_constant_evaluated())
				Throw("参数无效");
			else
				return 0;
		}
		if (num == 1)
			return 0;
		uint_fast8_t result = 1;
		for (T value = base; value < num; value *= base)
			result++;
		return result;
	}
	/// Log函数常函数，向上取整
	template <auto... V, typename... T> requires(sizeof...(T) < 2)
	constexpr auto LogCeil(T... p) { return LogCeil(V..., p...); }

	/// 指数函数常函数
	template <typename T>
	constexpr T Exp(T base, uint_fast8_t times)
	{
		if (times == 0)
		{
			pw_pbl_assert(base != 0, "参数无效");
			return 1;
		}
		T result = base;
		while (--times)
			if (MulOverflow(base, &result))
				return 0;
		return result;
	}

	/// 指数函数常函数
	template <auto base>
	constexpr auto Exp(uint_fast8_t times)
	{
		if constexpr (base == 1)
			return base;
		else if constexpr (base == 2)
		{
			using T = decltype(base);
			if (constexpr auto maxbits = sizeof(T) * CHAR_BIT - (std::is_signed_v<T> ? 1 : 0); times >= maxbits)
				return 0;
			return T{T{1} << times};
		}
		else
			return Exp(base, times);
	}

	/// 指数函数常函数
	template <auto base, uint_fast8_t times>
	constexpr auto Exp() { return Const<Exp<base>(times)>; }

	/// 类型占用二进制位数的运算常函数
	template <typename T>
	constexpr size_t BitCntOf = sizeof(T) * CHAR_BIT;

	template <size_t BITS>
	constexpr size_t BitCntOf<UBitInt<BITS>> = BITS;

	template <size_t BITS>
	constexpr size_t BitCntOf<SBitInt<BITS>> = BITS;

	template <std::integral T>
	constexpr size_t bit_width(T v) noexcept
	{
		if (v == 0)
			return 0;
		if constexpr (std::unsigned_integral<T>)
			return std::bit_width(v);
		else if (v > 0)
			return std::bit_width(std::make_unsigned_t<T>(v));
		else
			return std::bit_width(std::make_unsigned_t<T>(-v)) + !IsPow2(-v);
	}

	template <typename T>
	constexpr T AlignUp(T value, size_t align) noexcept
	{
		if (std::is_constant_evaluated() && !IsPow2(align))
			Throw("对齐需要是2的幂");
		auto mask = T(align - 1);
		return (value + mask) & ~mask;
	}

	template <size_t align, typename T>
	requires(IsPow2(align)) constexpr T AlignUp(T value) noexcept
	{
		constexpr auto mask = T(align - 1);
		return (value + mask) & ~mask;
	}

	template <typename T>
	constexpr T AlignDown(T value, size_t align) noexcept
	{
		if (std::is_constant_evaluated() && !IsPow2(align))
			Throw("对齐需要是2的幂");
		return value & ~T(align - 1);
	}

	template <size_t align, typename T>
	requires(IsPow2(align)) constexpr T AlignDown(T value) noexcept
	{
		constexpr auto mask = T(align - 1);
		return value & ~mask;
	}

	/// 向上取整除法，注意除数必须大于0
	template <std::unsigned_integral T>
	constexpr T CeilDivide(T value, std::type_identity_t<T> divisor) noexcept
	{
		if (std::is_constant_evaluated() && divisor == 0)
			Throw("除数必须大于0");
		return (divisor - 1 + value) / divisor;
	}

	/// 向上取整除法，注意除数必须大于0
	template <std::signed_integral T>
	consteval T CeilDivide(T value, std::type_identity_t<T> divisor) noexcept
	{
		if (value < 0 || divisor <= 0)
			Throw("除数必须大于0，被除数必须大于等于0");
		return (divisor - 1 + value) / divisor;
	}

	/// 向上取整除法，注意除数必须大于0
	template <std::integral T, T divisor> requires(divisor > 0)
	constexpr T CeilDivide(T value) noexcept
	{
		constexpr auto extra = divisor - 1;
		return (extra + value) / divisor;
	}

	/// 向上取整除法的除数对象
	template <std::unsigned_integral T>
	struct CeilDivisior
	{
		T value;

		inline constexpr CeilDivisior(T v) noexcept : value(v)
		{
			if (std::is_constant_evaluated() && v == 0)
				Throw("除数必须大于0");
		}
		inline consteval CeilDivisior(std::make_signed_t<T> v) noexcept : value(v)
		{
			if (v <= 0)
				Throw("除数必须大于0");
		}
	};
	template <std::integral T>
	CeilDivisior(T) -> CeilDivisior<std::make_unsigned_t<T>>;

	template <std::integral O, std::unsigned_integral T>
	constexpr O operator/(O va, const CeilDivisior<T> &divisor) noexcept { return CeilDivide(va, {divisor.value}); }

} // namespace pw_pbl::Math

namespace pw_pbl
{
	namespace [[deprecated("use Math instead")]] ConstMath
	{
		using namespace Math;
	}
} // namespace pw_pbl

#endif // PW_PBL_MATH_HPP
